翻訳と辞書 Words near each other ・ Domaszno ・ Domaszowice, Opole Voivodeship ・ Domaszowice, Świętokrzyskie Voivodeship ・ Domaszék ・ Domaszów ・ Domasław ・ Domasław, Lower Silesian Voivodeship ・ Domasławice ・ Domasławice, Lower Silesian Voivodeship ・ Domasławice, West Pomeranian Voivodeship ・ Domasłów ・ Domat ・ Domat/Ems ・ Domat/Ems (Rhaetian Railway station) ・ Domata Peko ・ Domatic number ・ Domatium ・ Domatków ・ Domatoceras ・ Domatowo ・ Domats ・ Domatówko ・ Domazan ・ Domaćica ・ Domański ・ Domaňovce ・ Domaševo ・ Domašinec ・ Domašov ・ Domašov (disambiguation) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Domatic number ： ウィキペディア英語版 Domatic number In graph theory, a domatic partition of a graph $G\; =\; (V,E)$ is a partition of $V$ into disjoint sets $V\_1$, $V\_2$,...,$V\_K$ such that each ''Vi'' is a dominating set for ''G''. The figure on the right shows a domatic partition of a graph; here the dominating set $V\_1$ consists of the yellow vertices, $V\_2$ consists of the green vertices, and $V\_3$ consists of the blue vertices. The domatic number is the maximum size of a domatic partition, that is, the maximum number of disjoint dominating sets. The graph in the figure has domatic number 3. It is easy to see that the domatic number is ''at least'' 3 because we have presented a domatic partition of size 3. To see that the domatic number is ''at most'' 3, we first review a simple upper bound. ==Upper bounds== Let $\backslash delta$ be the minimum degree of the graph $G$. The domatic number of $G$ is at most $\backslash delta\; +\; 1$. To see this, consider a vertex $v$ of degree $\backslash delta$. Let $N$ consist of $v$ and its neighbours. We know that (1) each dominating set $V\_i$ must contain at least one vertex in $N$ (domination), and (2) each vertex in $N$ is contained in at most one dominating set $V\_i$ (disjointness). Therefore there are at most $|N|\; =\; \backslash delta\; +\; 1$ disjoint dominating sets. The graph in the figure has minimum degree $\backslash delta\; =\; 2$, and therefore its domatic number is at most 3. Hence we have shown that its domatic number is exactly 3; the figure shows a maximum-size domatic partition. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Domatic number」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.